﻿#pragma once
#include "Index.h"
class IFindKCloestElements
{
public:
	/**
	 * 找到 K 个最接近的元素
	 * https://leetcode.cn/problems/find-k-closest-elements/
	 *
	 * 给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
	 * 整数 a 比整数 b 更接近 x 需要满足：
	 * |a - x| < |b - x| 或者 |a - x| == |b - x| 且 a < b
	 */
	virtual std::vector<int> findClosestElements(std::vector<int>& arr, int k, int x) = 0;
};

class FindKCloestElements
{
public:
	class Solution:public IFindKCloestElements
	{
	public:
		std::vector<int> findClosestElements(std::vector<int>& arr, int k, int x) override
		{
			if (arr.size() <= k)
				return arr;

			//首个更靠近x的位置
			const int cloestIndex = findFirstCloestIndex(arr, x);

			//往两边扩展,找到k个最靠近的数
			std::vector<int> cloestElems = chooseKCloestElems(arr, k, x, cloestIndex);

			return cloestElems;
		}
	private:
		//arr[firstIndex]是否比arr[secondIndex]更靠近x?
		bool isCloserThan(std::vector<int>& arr,int x,int firstIndex,int secondIndex)
		{
			const int firstDelta = std::abs(arr[firstIndex] - x);
			const int secondDelta = std::abs(arr[secondIndex] - x);
			return (firstDelta < secondDelta || (firstDelta == secondDelta && firstIndex < secondIndex));
		}
		//利用二分法找到首个最接近x的数
		int findFirstCloestIndex(std::vector<int>& arr, int x)
		{
			const int arrSize = arr.size();

			//利用二分法找到首个最接近x的数
			int left = 0, right = arrSize - 1;
			//开始前更靠近x的位置
			int cloestIndex = std::abs(arr.front() - x) <= std::abs(arr.back() - x) ? left : right;
			//与x的决定值偏移
			int cloestDelta = std::abs(arr[cloestIndex] - x);
			while (left <= right)
			{
				const int mid = (left + right) >> 1;
				const int midDelta = std::abs(arr[mid] - x);
				//尝试找到更靠近x的位置
				if (midDelta < cloestDelta || (midDelta == cloestDelta && mid < cloestIndex))
				{
					cloestIndex = mid;
					cloestDelta = midDelta;
				}

				if (arr[mid] < x)
					left = mid + 1;
				else
					right = mid - 1;
			}

			return cloestIndex;
		}
		//根据首个最靠近x的位置cloestIndex，往左右两边扩展，直到选出k个最靠近的元素.返回的元素按照从小到达排序
		std::vector<int> chooseKCloestElems(std::vector<int>& arr, int k, int x,int cloestIndex)
		{
			const int arrSize = arr.size();

			int cloestElemsSize = 0;
			std::list<int> cloestElems;

			int left = cloestIndex - 1, right = cloestIndex;
			while (cloestElemsSize < k)
			{
				//边界是否合法
				const bool leftValid = left >= 0;
				const bool rightValid = right < arrSize;

				//是否选择左指针的位置作为下一个靠近x的数?，为false的话就选择右指针位置
				bool chooseLeft = false;
				if (leftValid && rightValid)
				{
					if (isCloserThan(arr, x, left, right))
						chooseLeft = true;
				}
				else if (leftValid)
					chooseLeft = true;
				else if (rightValid)
					chooseLeft = false;
				else
					break;

				if (chooseLeft)
					cloestElems.push_front(arr[left--]);
				else
					cloestElems.push_back(arr[right++]);
				cloestElemsSize++;
			}

			return { cloestElems.begin(),cloestElems.end() };
		}
	};
};